#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 912. 排序数组.py
@time: 2022/1/5 16:53
@desc: https://leetcode-cn.com/problems/sort-an-array/
@解题思路&难点：
    1. 使用快排时。在一个特别长的数组而且又有序的情况下效率很低
    2. 因此选取pivot时，应随机取一个数跟low的位置交换，而不是直接取low，来打破有序情况
    3. Ot(nlogn), Os(height)递归栈层数

    1. 使用堆排序: Ot(nlogn), Os(1)，初始化堆需要O(n), 一次调整需要O(logn), n-1次调整需要O(nlogn)
'''
import random
class Solution(object):
    def pivot(self, nums, low, high):
        idx = random.randint(low, high)
        nums[low], nums[idx] = nums[idx], nums[low]
        piv = nums[low]
        while low<high:
            while low<high and nums[high]>=piv: high-=1
            nums[low] = nums[high]
            while low<high and nums[low]<=piv: low+=1
            nums[high] = nums[low]
        nums[low] = piv
        return low

    def quick_sort(self, nums, low, high):
        if low<high:
            piv = self.pivot(nums, low, high)
            self.quick_sort(nums, low, piv-1)
            self.quick_sort(nums, piv+1, high)
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        self.quick_sort(nums, 0, len(nums)-1)
        return nums

class Solution2(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        def pivot(nums, low, high):
            idx = random.randint(low, high)
            nums[idx], nums[low] = nums[low], nums[idx]
            piv = nums[low]
            while low<high:
                while low<high and piv<=nums[high]: high-=1
                nums[low] = nums[high]
                while low<high and piv>=nums[low]: low += 1
                nums[high] = nums[low]
            nums[low] = piv
            return low
        def quick_sort(nums, low, high):
            if low>=high: return
            piv = pivot(nums, low, high)
            quick_sort(nums, low, piv-1)
            quick_sort(nums, piv+1, high)

        quick_sort(nums, 0, len(nums)-1)
        return nums

# 堆排序
class Solution03:
    def max_heapify(self, heap, root, heap_len):
        """
        调整堆
        :param heap: 堆数组
        :param root: 根节点
        :param heap_len: 堆长度
        :return:
        """
        # 根节点的位置
        p = root
        # 若其有左右子树
        while p * 2 + 1 < heap_len:
            # 左、右子树的位置
            l, r = p * 2 + 1, p * 2 + 2
            # 以下步骤是为取左右子树中的最大值
            # 若没有右子树，即右子树下标超出了边界，或者左子树比右子树大就取左子树的下标为考察的对象
            if heap_len <= r or heap[r] < heap[l]:
                nex = l
            # 反之则取右子树考察
            else:
                nex = r
            # 如果考察的对象nex大于当前根节点p，就交换位置，即使原来的p现在去到了nex的位置，然后递归考察原来的p结点，所以将nex赋值与p结点
            if heap[p] < heap[nex]:
                heap[p], heap[nex] = heap[nex], heap[p]
                p = nex
            else:
                break

    def build_heap(self, heap):
        # 从最右的叶子节点开始调整一次，使其富有最大堆的特性，即是根节点大于所有子节点
        for i in range(len(heap) - 1, -1, -1):
            self.max_heapify(heap, i, len(heap))

    def heap_sort(self, nums):
        # 将nums转换为大顶堆，堆顶为最大值
        self.build_heap(nums)
        # 从后往前遍历，每次将最大值放到[i]的位置，然后对[0, i-1]进行调整, 重复这个过程
        for i in range(len(nums) - 1, -1, -1):
            nums[i], nums[0] = nums[0], nums[i]
            self.max_heapify(nums, 0, i)

    def sortArray(self, nums: list) -> list:
        self.heap_sort(nums)
        return nums
# 归并排序
class Solution04:
    def sortArray(self, nums: list) -> list:
        def mergeSort(nums, low, high):
            if low==high: return
            mid = (low+high)>>1
            # 递归对两个区间排序:
            mergeSort(nums, low, mid)
            mergeSort(nums, mid+1, high)
            # 将两个区间合并
            tmp = []
            i, j = low, mid+1
            while i<=mid and j<=high:
                if nums[i]<nums[j]:
                    tmp.append(nums[i])
                    i += 1
                else:
                    tmp.append(nums[j])
                    j += 1
            while i<=mid:
                tmp.append(nums[i])
                i += 1
            while j<=high:
                tmp.append(nums[j])
                j += 1
            nums[low: high+1] = tmp
        mergeSort(nums, 0, len(nums)-1)
        return nums

if __name__ == '__main__':
    inp = [-2,3,-5]
    # Solution().quick_sort(inp, 0 ,len(inp)-1)
    Solution04().sortArray(inp)
    print(inp)